{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"https://habrastorage.org/web/677/8e1/337/6778e1337c3d4b159d7e99df94227cb2.jpg\"/>\n",
    "## Специализация \"Машинное обучение и анализ данных\"\n",
    "<center>Автор материала: программист-исследователь Mail.Ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ [Юрий Кашницкий](https://yorko.github.io/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center> Capstone проект №1 <br>Идентификация пользователей по посещенным веб-страницам\n",
    "<img src='http://i.istockimg.com/file_thumbview_approve/21546327/5/stock-illustration-21546327-identification-de-l-utilisateur.jpg'>\n",
    "\n",
    "# <center>Неделя 2. Подготовка и первичный анализ данных\n",
    "\n",
    "На второй неделе мы продолжим подготавливать данные для дальнейшего анализа и построения прогнозных моделей. Конкретно, раньше мы определили что сессия – это последовательность из 10 посещенных пользователем сайтов, теперь сделаем длину сессии параметром, и потом при обучении прогнозных моделей выберем лучшую длину сессии.\n",
    "Также мы познакомимся с предобработанными данными и статистически проверим первые гипотезы, связанные с нашими наблюдениями. \n",
    "\n",
    "**План 2 недели:**\n",
    " - Часть 1. Подготовка нескольких обучающих выборок для сравнения\n",
    " - Часть 2. Первичный анализ данных, проверка гипотез\n",
    "\n",
    "**В этой части проекта Вам могут быть полезны  следующие видеозаписи лекций курса \"Построение выводов по данным\":**\n",
    "\n",
    "   - [Доверительные интервалы для доли](https://www.coursera.org/learn/stats-for-data-analysis/lecture/3oi53/dovieritiel-nyie-intiervaly-dlia-doli)\n",
    "   - [Биномиальный критерий для доли](https://www.coursera.org/learn/stats-for-data-analysis/lecture/JwmBw/binomial-nyi-kritierii-dlia-doli)\n",
    "   - [Доверительные интервалы на основе бутстрепа](https://www.coursera.org/learn/stats-for-data-analysis/lecture/GZjW7/dovieritiel-nyie-intiervaly-na-osnovie-butstriepa)\n",
    "   \n",
    "**Кроме того, в задании будут использоваться библиотеки Python [glob](https://docs.python.org/3/library/glob.html), [pickle](https://docs.python.org/2/library/pickle.html), [itertools](https://docs.python.org/3/library/itertools.html) и класс [csr_matrix](https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csr_matrix.html) из scipy.sparse.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задание\n",
    "1. Заполните код в этой тетрадке \n",
    "2. Если вы проходите специализацию Яндеса и МФТИ, пошлите файл с ответами в соответствующем Programming Assignment. <br> Если вы проходите курс ODS, выберите ответы в [веб-форме](https://docs.google.com/forms/d/13ZnT7w7foHD0uw0ynTtj7atdiCGvlltF8ThhbJCvLsc).  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 1. Подготовка нескольких обучающих выборок для сравнения\n",
    "\n",
    "Пока мы брали последовательности из 10 сайтов, и это было наобум. Давайте сделаем число сайтов в сессии параметром, чтоб в дальнейшем сравнить модели классификации, обученные на разных выборках – с 5, 7, 10 и 15 сайтами в сессии. Более того, пока мы брали по 10 сайтов подряд, без пересечения. Теперь давайте применим идею скользящего окна – сессии будут перекрываться. \n",
    "\n",
    "**Пример**: для длины сессии 10 и ширины окна 7 файл из 30 записей породит не 3 сессии, как раньше (1-10, 11-20, 21-30), а 5 (1-10, 8-17, 15-24, 22-30, 29-30). При этом в предпоследней сессии будет один ноль, а в последней – 8 нолей.\n",
    "\n",
    "Создадим несколько выборок для разных сочетаний параметров длины сессии и ширины окна. Все они представлены в табличке ниже:\n",
    "\n",
    "<style type=\"text/css\">\n",
    ".tg  {border-collapse:collapse;border-spacing:0;}\n",
    ".tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}\n",
    ".tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;}\n",
    "</style>\n",
    "<table class=\"tg\">\n",
    "  <tr>\n",
    "    <th class=\"tg-031e\">session_length -&gt;<br>window_size <br></th>\n",
    "    <th class=\"tg-031e\">5</th>\n",
    "    <th class=\"tg-031e\">7</th>\n",
    "    <th class=\"tg-031e\">10</th>\n",
    "    <th class=\"tg-031e\">15</th>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td class=\"tg-031e\">5</td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td class=\"tg-031e\">7</td>\n",
    "    <td class=\"tg-031e\"></td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "  </tr>\n",
    "  <tr>\n",
    "    <td class=\"tg-031e\">10</td>\n",
    "    <td class=\"tg-031e\"></td>\n",
    "    <td class=\"tg-031e\"></td>\n",
    "    <td class=\"tg-031e\"><font color='green'>v</font></td>\n",
    "    <td class=\"tg-031e\">v</td>\n",
    "  </tr>\n",
    "</table>\n",
    "\n",
    "Итого должно получиться 18 разреженных матриц – указанные в таблице 9 сочетаний параметров формирования сессий для выборок из 10 и 150 пользователей. При этом 2 выборки мы уже сделали в прошлой части, они соответствуют сочетанию параметров: session_length=10, window_size=10, которые помечены в таблице выше галочкой зеленого цвета (done)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализуйте функцию *prepare_sparse_train_set_window*.\n",
    "\n",
    "Аргументы:\n",
    "- *path_to_csv_files* – путь к каталогу с csv-файлами\n",
    "- *site_freq_path* – путь к pickle-файлу с частотным словарем, полученным в 1 части проекта\n",
    "- *session_length* – длина сессии (параметр)\n",
    "- *window_size* – ширина окна (параметр) \n",
    "\n",
    "Функция должна возвращать 2 объекта:\n",
    "- разреженную матрицу *X_sparse* (двухмерная Scipy.sparse.csr_matrix), в которой строки соответствуют сессиям из *session_length* сайтов, а *max(site_id)* столбцов – количеству посещений *site_id* в сессии. \n",
    "- вектор *y* (Numpy array) \"ответов\" в виде ID пользователей, которым принадлежат сессии из *X_sparse*\n",
    "\n",
    "Детали:\n",
    "- Модифицируйте созданную в 1 части функцию *prepare_train_set*\n",
    "- Некоторые сессии могут повторяться – оставьте как есть, не удаляйте дубликаты\n",
    "- Замеряйте время выполнения итераций цикла с помощью *time* из *time*, *tqdm* из *tqdm* или с помощью виджета [log_progress](https://github.com/alexanderkuk/log-progress) ([статья](https://habrahabr.ru/post/276725/) о нем на Хабрахабре)\n",
    "- 150 файлов из *capstone_websites_data/150users/* должны обрабатываться за несколько секунд (в зависимости от входных параметров). Если дольше – не страшно, но знайте, что функцию можно ускорить. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import division, print_function\n",
    "# отключим всякие предупреждения Anaconda\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')\n",
    "from glob import glob\n",
    "import os\n",
    "import pickle\n",
    "from tqdm import tqdm_notebook\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from scipy.sparse import csr_matrix\n",
    "from scipy import stats\n",
    "from statsmodels.stats.proportion import proportion_confint\n",
    "%matplotlib inline\n",
    "from matplotlib import pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Поменяйте на свой путь к данным\n",
    "PATH_TO_DATA = 'capstone_user_identification'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prepare_sparse_train_set_window(path_to_csv_files, site_freq_path, \n",
    "                                    session_length=10, window_size=10):\n",
    "    ''' ВАШ КОД ЗДЕСЬ'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Примените полученную функцию с параметрами *session_length=5* и *window_size=3* к игрушечному примеру. Убедитесь, что все работает как надо.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_toy_s5_w3, y_s5_w3 = prepare_sparse_train_set_window(os.path.join(PATH_TO_DATA,'3users'), \n",
    "                                                       os.path.join(PATH_TO_DATA,'site_freq_3users.pkl'),\n",
    "                                       session_length=5, window_size=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_toy_s5_w3.todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y_s5_w3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Запустите созданную функцию 16 раз с помощью циклов по числу пользователей num_users (10 или 150), значениям параметра *session_length* (15, 10, 7 или 5) и значениям параметра *window_size* (10, 7 или 5). Сериализуйте все 16 разреженных матриц (обучающие выборки) и векторов (метки целевого класса – ID пользователя) в файлы `X_sparse_{num_users}users_s{session_length}_w{window_size}.pkl` и `y_{num_users}users_s{session_length}_w{window_size}.pkl`.**\n",
    "\n",
    "**Чтоб убедиться, что мы все далее будем работать с идентичными объектами, запишите в список *data_lengths* число строк во всех полученных рареженных матрицах (16 значений). Если какие-то будут совпадать, это нормально (можно сообразить, почему).**\n",
    "\n",
    "**На моем ноутбуке этот участок кода отработал за 26 секунд, хотя понятно, что все зависит от эффективности реализации функции *prepare_sparse_train_set_window* и мощности используемого железа. И честно говоря, моя первая реализация была намного менее эффективной (34 минуты), так что тут у Вас есть возможность оптимизировать свой код.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "import itertools\n",
    "\n",
    "data_lengths = []\n",
    "\n",
    "for num_users in [10, 150]:\n",
    "    for window_size, session_length in itertools.product([10, 7, 5], [15, 10, 7, 5]):\n",
    "        if window_size <= session_length and (window_size, session_length) != (10, 10):\n",
    "            X_sparse, y = ''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<font color='red'> Вопрос 1. </font>Сколько всего уникальных значений в списке `data_lengths`?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 2. Первичный анализ данных, проверка гипотез"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Считаем в DataFrame подготовленный на 1 неделе файл `train_data_10users.csv`. Далее будем работать с ним.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_df = pd.read_csv(os.path.join(PATH_TO_DATA, 'train_data_10users.csv'), \n",
    "                       index_col='session_id')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_df.info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Распределение целевого класса:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_df['user_id'].value_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Посчитаем распределение числа уникальных сайтов в каждой сессии из 10 посещенных подряд сайтов.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_unique_sites = [np.unique(train_df.values[i, :-1]).shape[0] \n",
    "                    for i in range(train_df.shape[0])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pd.Series(num_unique_sites).value_counts()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pd.Series(num_unique_sites).hist();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Проверьте с помощью QQ-плота и критерия Шапиро-Уилка, что эта величина распределена нормально**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<font color='red'> Вопрос 2. </font>Распределено ли нормально число уникальных сайтов в каждой сессии из 10 посещенных подряд сайтов (согласно критерию Шапиро-Уилка)?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Проверьте гипотезу о том, что пользователь хотя бы раз зайдет на сайт, который он уже ранее посетил в сессии из 10 сайтов. Давайте проверим с помощью биномиального критерия для доли, что доля случаев, когда пользователь повторно посетил какой-то сайт (то есть число уникальных сайтов в сессии < 10) велика: больше 95% (обратите внимание, что альтернатива тому, что доля равна 95% –  одностороняя). Ответом на 3 вопрос в тесте будет полученное p-value.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<font color='red'> Вопрос 3. </font>Каково p-value при проверке описанной гипотезы?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "has_two_similar = (np.array(num_unique_sites) < 10).astype('int')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pi_val = stats.binom_test  ''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<font color='red'> Вопрос 4. </font>Каков 95% доверительный интервал Уилсона для доли случаев, когда пользователь повторно посетил какой-то сайт (из п. 3)?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wilson_interval = ''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('{} {}'.format(round(wilson_interval[0], 3),\n",
    "                                   round(wilson_interval[1], 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Постройте распределение частоты посещения сайтов (сколько раз тот или иной сайт попадается в выборке) для сайтов, которые были посещены как минимум 1000 раз.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "site_freqs = ''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Постройте 95% доверительный интервал для средней частоты появления сайта в выборке (во всей, уже не только для тех сайтов, что были посещены как минимум 1000 раз) на основе bootstrap. Используйте столько же bootstrap-подвыборок, сколько сайтов оказалось в исходной выборке по 10 пользователям. Берите подвыборки из посчитанного списка частот посещений сайтов – не надо заново считать эти частоты. Учтите, что частоту появления нуля (сайт с индексом 0 появлялся там, где сессии были короче 10 сайтов) включать не надо. Округлите границы интервала до 3 знаков после запятой и запишите через пробел в файл *answer2_5.txt*. Это будет ответом на 5 вопрос теста.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<font color='red'> Вопрос 5. </font>Каков 95% доверительный интервал для средней частоты появления сайта в выборке?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_bootstrap_samples(data, n_samples, random_seed=17):\n",
    "    np.random.seed(random_seed)\n",
    "    indices = np.random.randint(0, len(data), (n_samples, len(data)))\n",
    "    samples = data[indices]\n",
    "    return samples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stat_intervals(stat, alpha):\n",
    "    boundaries = np.percentile(stat, \n",
    "                 [100 * alpha / 2., 100 * (1 - alpha / 2.)])\n",
    "    return boundaries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' ВАШ КОД ЗДЕСЬ '''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Пути улучшения\n",
    "Что еще можно добавить по второй части проекта:\n",
    "- можно дополнительно рассматривать сессии с параметром – длиной сессии по времени. И составить выборки, скажем, для 5-, 10-, 15- и 20-минутных сессий (это как раз пригодится в [соревновании](https://inclass.kaggle.com/c/catch-me-if-you-can-intruder-detection-through-webpage-session-tracking2) Kaggle Inclass)\n",
    "- можно провести больше первичного анализа и проверять прочие интересные гипотезы (а больше их появится после создания признаков на следующей неделе)\n",
    "\n",
    "На 3 неделе мы займемся визуальным анализом данных и построением признаков."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
